package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 2360. 图中的最长环
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/2 13:48
 */
public class LongestCycle {

    public static void main(String[] args) {
        LongestCycle test = new LongestCycle();

        // 3
//        int[] arr = {3, 3, 4, 2, 3};

        // -1
//        int[] arr = {-1, 4, -1, 2, 0, 4};

        // -1
//        int[] arr = {2, -1, 3, 1};

        // 3
//        int[] arr = {3, 3, 4, 2, 3};

        //
//        int length = 100000;
//        int[] arr = Utils.getArr(length, -1, length - 1);
        //
        String path = "C:\\lw\\aa.txt";
        int[] arr = Utils.getArr(path);


        long a = System.currentTimeMillis();

        int i = test.longestCycle(arr);

        long b = System.currentTimeMillis();
        System.out.println(b - a);
        System.out.println(i);
    }

    public int longestCycle(int[] edges) {
        int max = -1;
        int length = edges.length;
        int[] arr = new int[length];
        int[] arr2 = new int[length];
        for (int i = 0; i < length; i++) {
            if (arr[i] > 0 || arr[i] == -1) {
                continue;
            }
            int item = i;
            int count = 1;
            while (item != -1) {
                if (arr[item] == 0) {
                    arr2[item] = i + 1;
                    arr[item] = count++;
                    item = edges[item];
                } else {
                    if (arr2[item] == i + 1) {
                        max = Math.max(max, count - arr[item]);
                    }
                    break;
                }
            }
        }
        return max;
    }

}
